/*
 * Alloy Analyzer
 * Copyright (c) 2002 Massachusetts Institute of Technology
 *
 * The Alloy Analyzer is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * The Alloy Analyzer is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with the Alloy Analyzer; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package alloy.util;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * Iterator for iterating over a fixed-size multidimensional array of arbitrary dimension,
 * with the dimension specified at runtime in the iterator's constructor.
 * <p>
 * For a given set of dimensions, it is guaranteed to yield the same sequence
 * of indices every time it is created.
 * <p>
 * The set of dimensions may be empty, in which case we're iterating over a zero-dimensional
 * array, i.e. a scalar.  In that case we yield an empty coordinate sequence once,
 * and then say that there are no more elements.
 */
public final class MultiDimIter implements ResettableIterator {
    /** The size of each dimension */
    private int[] _dims;
    
    /** The current value in each dimension */
    private int[] _cur;
    
    /** Total number of elements to return */
    private long _totalElems;
    
    /** Elements returned so far */
    private int _elemsReturned;
    
    /** Enumeration order.  If null, use standard order. */
    private int[] _enumOrder = null;

    public MultiDimIter(int[] dims_, int[] enumOrder_) {
	this._dims = dims_; this._cur = new int[dims_.length]; this._enumOrder = enumOrder_;
	_totalElems = 1;
	for (int i=0; i<dims_.length; i++)
	    _totalElems *= dims_[i];
    }
    public MultiDimIter(int[] dims_) { this(dims_, null); }

    public boolean hasNext() { return _elemsReturned < _totalElems; }

    public void rewind() {
	Arrays.fill(_cur, 0);
	_elemsReturned = 0;
    }

    public int[] getDims() { return _dims; }

    /**
     * Return the flat index of the last element whose indices were
     * returned by {@link #next}
     */
    public int getFlatInd() { return _elemsReturned-1; }
	
    /** Return the next array of indices.  <em>Note</em>: the same array is returned on each
	{@link #next} call, with only the contents modified; if you need to keep a pointer
	to this array, be sure to clone it! */
    public Object next() {
	if (!hasNext()) throw new NoSuchElementException("MultiDimIter.next()");
	if (_elemsReturned > 0) {
	    int i = _cur.length-1;
	    while(i>=0  &&  _cur[_ind(i)] == _dims[_ind(i)]-1) {
		_cur[_ind(i)] = 0;
		i--;
	    }
	    if (i >= 0) _cur[_ind(i)]++;
	}
	_elemsReturned++;
	return _cur;
    }
    
    public void remove() throws UnsupportedOperationException
    { throw new UnsupportedOperationException("MultiDimIter.remove()"); }

    /** Transform index by {@link #_enumOrder} if an enumeration order is given,
	otherwise return the index unchanged. */
    private int _ind(int i) { return _enumOrder==null ? i : _enumOrder[i]; }
}
